package com.shm.leetcode;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

/**
 * 76. 最小覆盖子串
 * 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
 *
 * 注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。
 *
 *
 *
 * 示例 1：
 *
 * 输入：s = "ADOBECODEBANC", t = "ABC"
 * 输出："BANC"
 * 示例 2：
 *
 * 输入：s = "a", t = "a"
 * 输出："a"
 *
 *
 * 提示：
 *
 * 1 <= s.length, t.length <= 105
 * s 和 t 由英文字母组成
 *
 *
 * 进阶：你能设计一个在 o(n) 时间内解决此问题的算法吗？
 * @author SHM
 */
public class MinWindow {
    HashMap<Character,Integer> tMap = new HashMap<>();
    HashMap<Character,Integer> cnt = new HashMap<>();

    /**
     * 方法一：双指针
     * 思路和算法
     *
     * 本问题要求我们返回字符串 ss 中包含字符串 tt 的全部字符的最小窗口。我们称包含 tt 的全部字母的窗口为「可行」窗口。
     *
     * 我们可以用双指针的思想解决这个问题。使用两个指针，其中 rr 用于「延伸」现有窗口，ll 用于「收缩」现有窗口。在任意时刻，只有一个指针运动，而另一个保持静止。我们在 ss 上使用双指针，通过移动 rr 指针不断扩张窗口，当窗口包含 tt 全部所需的字符后，如果能收缩，我们就收缩窗口直到得到最小窗口。
     *
     *
     *
     * 如何判断当前的窗口包含所有 tt 所需的字符呢？我们可以用一个哈希表表示 tt 中所有的字符以及它们的个数，用一个哈希表动态维护窗口中所有的字符以及它们的个数，如果这个动态表中包含 tt 的哈希表中的所有字符，并且对应的个数都不小于 tt 的哈希表中各个字符的个数，那么当前的窗口是「可行」的。
     *
     * 注意：这里 tt 中可能出现重复的字符，所以我们要记录字符的个数。
     *
     * 考虑如何优化？ 如果 s = {\rm XX \cdots XABCXXXX}s=XX⋯XABCXXXX，t = {\rm ABC}t=ABC，那么显然 {\rm [XX \cdots XABC]}[XX⋯XABC] 是第一个得到的「可行」区间，得到这个可行区间后，我们按照「收缩」窗口的原则更新左边界，得到最小区间。我们其实做了一些无用的操作，就是更新右边界的时候「延伸」进了很多无用的 \rm XX，更新左边界的时候「收缩」扔掉了这些无用的 \rm XX，做了这么多无用的操作，只是为了得到短短的 \rm ABCABC。没错，其实在 ss 中，有的字符我们是不关心的，我们只关心 tt 中出现的字符，我们可不可以先预处理 ss，扔掉那些 tt 中没有出现的字符，然后再使用双指针呢？也许你会说，这样可能出现 \rm XXABXXCXXABXXC 的情况，在统计长度的时候可以扔掉前两个 \rm XX，但是不扔掉中间的 \rm XX，怎样解决这个问题呢？优化后的时空复杂度又是多少？这里代码给出没有优化的版本，以上的三个问题留给读者思考，欢迎大家在评论区给出答案哟
     *
     * 复杂度分析
     *
     * 时间复杂度：最坏情况下左右指针对 ss 的每个元素各遍历一遍，哈希表中对 ss 中的每个元素各插入、删除一次，对 tt 中的元素各插入一次。每次检查是否可行会遍历整个 tt 的哈希表，哈希表的大小与字符集的大小有关，设字符集大小为 CC，则渐进时间复杂度为 O(C\cdot |s| + |t|)O(C⋅∣s∣+∣t∣)。
     * 空间复杂度：这里用了两张哈希表作为辅助空间，每张哈希表最多不会存放超过字符集大小的键值对，我们设字符集大小为 CC ，则渐进空间复杂度为 O(C)O(C)。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/minimum-window-substring/solution/zui-xiao-fu-gai-zi-chuan-by-leetcode-solution/
     * @param s
     * @param t
     * @return
     */
    public String minWindow(String s, String t) {
        for (char c : t.toCharArray()) {
            tMap.put(c,tMap.getOrDefault(c,0)+1);
        }
        int left = 0,right = -1;
        int len = Integer.MAX_VALUE,ansL = -1,ansR = -1;
        int sLen = s.length();
        while (right<sLen){
            ++right;
            if(right<sLen&& tMap.containsKey(s.charAt(right))){
                cnt.put(s.charAt(right),cnt.getOrDefault(s.charAt(right),0)+1);
            }
            //
            while (check()&&left<=right){
                if(right-left+1<len){
                    len = right-left+1;
                    ansL = left;
                    //
                    ansR = right+1;
                }
                if(tMap.containsKey(s.charAt(left))){
                    cnt.put(s.charAt(left),cnt.getOrDefault(s.charAt(left),0)-1);
                }
                left++;
            }
        }
        return ansR==-1?"":s.substring(ansL,ansR);
    }
    boolean check(){
        Iterator<Map.Entry<Character, Integer>> iterator = tMap.entrySet().iterator();
        while (iterator.hasNext()){
            Map.Entry<Character, Integer> next = iterator.next();
            Character key = next.getKey();
            Integer value = next.getValue();
            if(cnt.getOrDefault(key,0)<value){
                return false;
            }
        }
        return true;
    }
}
